The present invention relates to the field of data communication and more particularly to techniques for optimizing bandwidth usage while controlling latency.
Applications such as online video games can produce large amounts of network traffic. Networks however have a limited capacity to convey information, and multiple computers and applications must share that limited resource. For example, networks such as the Internet connect several computers with network links having a limited bandwidth that is shared among the many computers, each of which wants to maximize its usage of available bandwidth. When attempted data rates exceed the network capacity to convey that data, the network congests and the effective network capacity becomes a small fraction of the theoretical capacity, so applications must throttle their usage to remain within available bandwidth.
Two types of protocols are generally used to communicate data between computers in a network environment, namely, reliable protocols and unreliable protocols. When computers transfer data reliably, they use protocols which detect and retransmit the dropped or lost packets. Accordingly, a reliable protocol (also referred to as “reliable transport protocol” or “reliable transport” or “reliable communication protocol”) is a type of network transport protocol which generally guarantees delivery, content integrity, and also generally the order of the data packets. When a network link becomes saturated with traffic (i.e., when the actual data rate meets or exceeds capacity), packet buffers fill up and excess packets may get dropped. For example, routers that are used to connect computers and networks together have packet buffers to accommodate small bursts of data packets. If the sustained data rate exceeds the available bandwidth, the router packet buffers get full, latency (i.e., the delay between when a sender sends and a receiver receives a data packet) increases and eventually packets are dropped. This triggers retransmission of the dropped data packets in a reliable protocol. However, if the network is congested, the retransmitted packets often also get dropped. This problem can (and often does) spiral downward into “congestion collapse” in which network links contain mostly retransmission attempts, most of which fail, and the net transfer rate reaches only a tiny fraction of the theoretical capacity of the link.
Several standard solutions are available for congestion avoidance and control for reliable transports. For example, the dominant reliable protocol of the Internet is Transmission Control Protocol (TCP). Several solutions are available for controlling and avoiding congestion for TCP that can be used by applications that use TCP for communications. Examples of such techniques are described in: (1) Floyd, S & Jacobsen, V (1993): “Random early detection gateways for congestion avoidance”, IEEE/ACM Transactions on Networking, August; and (2) Postel, J. (1981): “RFC 793: Transmission Control Protocol”, Internet Engineering Task Force, September.
In addition to reliable transport data (e.g., TCP data), the communication networks such as the Internet also carry traffic using unreliable transports (also referred to as “unreliable transport protocol” or “unreliable transport” or “unreliable communication protocol”) which do not guarantee delivery or order of the data packets. Some guarantee content integrity. Examples of such unreliable traffic include online game data and streaming audio and video data which make high demands on available network bandwidth. The User Datagram Protocol (UDP) (RFC 768) is the dominant “best effort” or unreliable protocol used on the Internet. Such unreliable communication protocols have no systematic, ubiquitous or standard congestion control system, partly because each application has specialized requirements. For example, online interactive games require keeping latency as low as possible, whereas the performance of most other applications suffers little or no negative consequences as latency increases.
Without congestion control, these unreliable data streams can saturate network links and defeat or unfairly compete with the congestion avoidance systems in TCP. Typically, these streams implicitly compete for bandwidth with unfair or unfriendly behaviors. Applications which do not detect and respond to changes in available bandwidth (the network link data rate capacity minus potential usage by other connections that share the same physical link) typically make assumptions about available bandwidth, and those assumptions can be either too small or too large, potentially resulting in inadequate performance, excessive packet loss and can interfere with protocols that perform congestion control (See: Floyd, S & Jacobsen, V (1993): “Random early detection gateways for congestion avoidance”, IEEE/ACM Transactions on Networking, August.).
Some nascent congestion control systems exist for unreliable traffic protocols as described in: (1) Padhye, J, Kurose, J, Towsley, D & Koodli, R (1998): “A TCP-friendly rate adjustment protocol for continuous media flows over best effort networks”, Technical Report 98 11, UMASS CMPSCI; (2) Sisalem, D & Schulzrinne, H (1998): “The loss-delay based adjustment algorithm: a TCP-friendly adaptation scheme”, German Ministry of Education and Research; (3) Jun Yi Lee (2003): “Performance analysis of binomial rate adaptation scheme for TCP-friendly congestion control”, student thesis, Department of Computer Science and Information Engineering, National Chung Cheng University, Chia-Yi, Taiwan, Republic of China; (4) Balakrishnan, H & Seshan, S (2001): “RFC 3124: The congestion manager”, Internet Engineering Task Force, June; (5) Liu, J, Li, B, Zhang, Y-Q (2001): “An end-to-end adaptation protocol for layered video multicast using optimal rate allocation”; and (6) Aboobaker, N, Chanady, D & Gerla, M. (2002): “Streaming media congestion control using bandwidth estimation”. However, most of these are aimed to work with streaming media, which typically has low sensitivity to large latencies. These techniques are inadequate for interactive media applications such as online games that are very sensitive to latencies.
Accordingly, conventional systems do not provide an adequate solution for achieving high bandwidth usage with low latency using unreliable protocols.